package com.java.linkedlist;

import java.util.Objects;
import java.util.Stack;

/**
 * 单链表的练习
 *
 * @author 19252
 */
public class SingleLinkedListPractice {

    public static void main(String[] args) {
        SingleLinkedListPractice practice = new SingleLinkedListPractice();
        HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星");
        HeroNode heroNode5 = new HeroNode(5, "关胜", "大刀");
        HeroNode heroNode7 = new HeroNode(7, "秦明", "霹雳火");
        // 创建链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        // 添加节点,顺序添加演示
        singleLinkedList.addNode(heroNode1);
        singleLinkedList.addNode(heroNode3);
        singleLinkedList.addNode(heroNode5);
        singleLinkedList.addNode(heroNode7);
        System.out.println("================> 链表生成 <=================");
        singleLinkedList.showLinkedList();
        System.out.println("================> 链表查找倒数第k个 <=================");
        System.out.println(practice.findLastIndexNode(singleLinkedList.getHead(), 4));
        System.out.println(practice.findLastIndexNode(singleLinkedList.getHead(), 5));
        System.out.println(practice.findLastIndexNode(singleLinkedList.getHead(), 1));
        System.out.println("================> 链表反转 <=================");
//        practice.reverseLinkedList(singleLinkedList.getHead());
        // practice.reverseLinkedListByStack(singleLinkedList.getHead());
        // singleLinkedList.showLinkedList();
        // System.out.println("================> 链表长度 <=================");
//        System.out.println(practice.getLinkedListLength(singleLinkedList.getHead()));
//        singleLinkedList.deleteNode(2);
//        System.out.println(practice.getLinkedListLength(singleLinkedList.getHead()));

        System.out.println("================> 链表合并 <=================");
        HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode heroNode4 = new HeroNode(4, "公孙胜", "入云龙");
        HeroNode heroNode6 = new HeroNode(6, "林冲", "豹子头");
        HeroNode heroNode8 = new HeroNode(8, "呼延灼", "双鞭");
        SingleLinkedList singleLinkedList2 = new SingleLinkedList();
        singleLinkedList2.addNodeByNo(heroNode2);
        singleLinkedList2.addNodeByNo(heroNode6);
        singleLinkedList2.addNodeByNo(heroNode4);
        singleLinkedList2.addNodeByNo(heroNode8);
        singleLinkedList2.showLinkedList();
        System.out.println("================> 合并结果 <=================");
        practice.mergeTowLinkedList(singleLinkedList.getHead(), singleLinkedList2.getHead(), singleLinkedList);
        singleLinkedList.showLinkedList();
    }

    /**
     * 获取单链表的有效长度
     *
     * @param heroNode 链表的头结点
     * @return 链表的有效长度
     */
    public int getLinkedListLength(HeroNode heroNode) {
        // 判断链表是否为空
        HeroNode temp = heroNode;
        boolean flag = Objects.nonNull(temp.getNext());
        int count = 0;
        while (flag) {
            count++;
            temp = temp.getNext();
            flag = Objects.nonNull(temp.getNext());
        }
        return count;
    }

    /**
     * 查找单链表中的倒数第 k 节点
     *
     * @param heroNode 头结点
     * @param index    节点位置
     * @return 倒数第 k 个节点
     */
    public HeroNode findLastIndexNode(HeroNode heroNode, int index) {
        HeroNode temp = heroNode;
        boolean flag = Objects.nonNull(temp.getNext());
        int length = getLinkedListLength(heroNode);
        // 链表不为空
        if (flag) {
            // 进行索引的合理性判断
            int i = length - index;
            // 合理在进行查询
            if (i >= 0) {
                for (int j = 0; j < i + 1; j++) {
                    temp = temp.getNext();
                }
                return temp;
            }
            System.out.println("你要查找的节点不存在！");
        } else {
            System.out.println("链表为空！");
        }
        return null;
    }

    /**
     * 链表反转
     *
     * @param heroNode 需要被反转的链表的头结点
     */
    public void reverseLinkedList(HeroNode heroNode) {
        // 辅助头结点
        HeroNode reverse = new HeroNode();
        // 临时变量
        HeroNode temp = heroNode.getNext();
        HeroNode current;
        HeroNode next;
        // 链表是否为空
        boolean flag = Objects.nonNull(temp);
        if (!flag) {
            System.out.println("链表为空！");
            return;
        }
        // 链表是否只有一个节点
        flag = Objects.nonNull(temp.getNext());
        if (!flag) {
            System.out.println("链表不需要反转！");
            return;
        }
        // 链表不是只有一个节点，则开始反转
        while (flag) {
            // 保存下一节点
            next = temp.getNext();
            // 位置置换
            current = temp;
            current.setNext(reverse.getNext());
            reverse.setNext(current);
            // 将保存好的下一个节点还原
            temp = next;
            // 节点判空
            flag = Objects.nonNull(temp);
        }
        // 链表反转
        heroNode.setNext(reverse.getNext());
    }

    /**
     * 使用堆栈的方法，反转输出链表
     * @param heroNode 链表头结点
     */
    public void reverseLinkedListByStack(HeroNode heroNode){
        HeroNode temp = heroNode;
        boolean flag = Objects.nonNull(temp.getNext());
        Stack<HeroNode> stack = new Stack<>();
        while (flag){
            // 入栈
            stack.push(temp.getNext());
            temp = temp.getNext();
            flag = Objects.nonNull(temp.getNext());
        }
        // 提前保留栈的值，否则栈的值是会随栈中的数据减少，变小
        int size = stack.size();
        for (int i = 0; i < size; i++) {
            // 出栈，反序输出
            System.out.println(stack.pop());
        }
    }

    /**
     * 合并两个有序链表
     * @param heroNode1 有序链表一的头结点
     * @param heroNode2 有序链表二的头结点
     */
    public void mergeTowLinkedList(HeroNode heroNode1, HeroNode heroNode2, SingleLinkedList singleLinkedList){
        HeroNode temp2 = heroNode2;
        boolean flag1 = Objects.nonNull(heroNode1.getNext());
        boolean flag2 = Objects.nonNull(temp2.getNext());
        // 链表一为空，链表二不为空
        if (!flag1 && flag2){
            heroNode1.setNext(heroNode2.getNext());
            return;
        }
        // 链表一不为空，链表二为空
        if (flag1 && !flag2){
            return;
        }
        // 两个链表都不为空在进行合并
        temp2 = heroNode2.getNext();
        while (flag2){
            HeroNode node = temp2.getNext();
            singleLinkedList.addNodeByNo(temp2);
            temp2 = node;
            flag2 = Objects.nonNull(temp2);
        }
    }
}
